Wireless networks interconnect a centralized communication system including a base station and one or more user nodes. Additionally, relay nodes can be interspersed between the base station and user nodes to extend range and quality of the communications link between the base station and user nodes.
Optimization of the network is a common problem in conventional fixed-base and user-node-based ad hoc wireless networks. Spanning tree algorithms are used to construct network trees connecting the base station to the user nodes through the relay nodes based on set parameters. For example, the tree that connects the base station to the user nodes using the least amount of relay nodes, the relay nodes with the best signal strength, or other consideration is determined. In the Steiner tree algorithm, a well-known NP-complete problem, a weighted tree with minimal weight that includes all user nodes is determined. However, the Steiner tree allows additional internal nodes to reduce the weight of the tree.
Development of mobile relay networks enables mobile relay nodes to autonomously move about an area to search for unconnected user nodes. Unlike conventional fixed-base and user-node-based ad hoc networks, which require placement of additional relay nodes or base stations to connect unconnected user nodes, mobile relay nodes can move and seek out additional user nodes in the environment. However, after initial deployment, disconnection, or breaking, of the existing connections between user nodes and the base station needs to be avoided during reconfiguration of the mobile relay nodes. Given an existing network configuration, the decision of which mobile relay nodes should stay in position and which mobile relay nodes should move is a problem.
Therefore, there is a need for an approach to maintain connectivity among existing user nodes and base stations while identifying mobile relay nodes that can be released from the network to seek connections with unconnected user nodes.